/*
https://www.acwing.com/problem/content/4231/

在一个 3×3的网格中，1∼8 这 8个数字和一个 X 恰好不重不漏地分布在这 3×3 的网格中。

例如：

1 2 3
X 4 6
7 5 8
在游戏过程中，可以把 X 与其上、下、左、右四个方向之一的数字交换（如果存在）。

把 X 与上下左右方向数字交换的行动记录为 u、d、l、r。

现在，给你一个初始网格状态，并希望你将其变换为一个目标网格状态，请你找到所需行动次数最少的方案。

我们用一行字符串来描述一种网格状态。

例如，网格：

1 2 3 
X 4 6 
7 5 8 
用 123X46758 来表示。

输入格式
第一行包含整数 T，表示共有 T 组测试数据。

每组数据占两行，第一行包含一个字符串表示初始网格状态，第二行包含一个字符串表示目标网格状态。

保证给定状态合法，并且一定有解。

输出格式
每组数据输出占两行，第一行输出 Case x: y，其中 x 为组别编号（从 1 开始），y 为所需最少行动次数。

第二行输出具体行动方案，如果方案不唯一，则输出字典序最小的方案。

数据范围
1≤T≤200
输入样例：
2
12X453786
12345678X
564178X23
7568X4123
输出样例：
Case 1: 2
dd
Case 2: 8
urrulldr
*/

#include<bits/stdc++.h>
using namespace std;
const int N = 100;

int T = 1;
int xb[10];
int path[N];
string now, endd;

int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, -1, 1, 0};
char op[4] ={'d', 'l', 'r', 'u'};

//估值函数，当前状态和目标状态每个点的曼哈顿距离差的和
int f()
{
    int res=0;

    for(int i=0; i < 9; i++)
    {
        if(now[i]!= 'X')
        {
            int t=now[i]-'0';
            res += abs(i / 3 - xb[t] / 3) + abs(i % 3 - xb[t] % 3);
        }
    }
    return res;
}


//因为 dfs 是一条路一条路的搜，并且有回溯。
//所以我们只需要一个 path 即可，后面的会覆盖前面的。
//同样 now 状态只需要一个，回溯会返回状态。

int depth;
bool dfs(int u)
{
    //如果当前深度 + 估值深度 > 最大深度 直接回溯
    if(f() + u > depth) return false;
    if(now == endd) return true; //找到答案了 直接return true

    int X;//找到 X 的位置
    for(int i = 0; i < 9; i++) 
    {
        if(now[i] == 'X') 
        {
            X = i;
            break;
        }
    }
    int x = X / 3, y = X % 3;

    for(int i = 0; i < 4; i++)
    {
        int zx = x + dx[i], zy = y + dy[i];

        //优化
        //避免无效操作： 上一个为 l 当前为 r，等于没变化
        if(u != 0 && i + path[u - 1] == 3) continue;
        if(zx < 0 || zx >= 3 || zy < 0 || zy >= 3) continue;

        //change
        swap(now[x * 3 + y], now[zx * 3 + zy]);
        path[u] = i;

        if(dfs(u + 1)) return true;
        //回复现场
        swap(now[x * 3 + y], now[zx * 3 + zy]);
    }

    return false;
}

void solved()
{
    cin >> now >> endd;

    //找到目标状态对应的下标
    for(int i = 0; i < 9; i++) xb[endd[i] - '0'] = i;

    for(depth = 0;; depth++) if(dfs(0)) break;

    cout << "Case " << T++ << ": " << depth << endl;
    for(int i  = 0; i < depth; i++) cout << op[path[i]];
    cout << endl;

}


int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        solved();
    }
    return 0;
}

 